package com.itheima.leetcode;

/**
 * 检测链表是否有环
 *
 * @FileName E10LeetCode141
 * @Description
 * @Author Sword
 * @date 2025-04-27
 **/
public class E10LeetCode141 {

    /*
        阶段1：
            龟一次走一步，兔子一次走两步
            当兔子能走到终点时，不存在环
            当兔子能追上龟时，可以判断存在环
        阶段2：
            从它们第一次相遇开始，龟回到起点，兔子保持原位不变
            龟和兔子一次都走一步
            当再次相遇时，地点就是环的入口
     */
    public static boolean hasCycle(ListNode head) {
        ListNode h = head;//兔子
        ListNode t = head;//乌龟

        while (h != null && h.next != null) {
            t = t.next;
            h = h.next.next;

            if (h == t) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        ListNode n12 = new ListNode(12, null);
        ListNode n11 = new ListNode(12, n12);
        ListNode n10 = new ListNode(12, n11);
        ListNode n9 = new ListNode(12, n10);
        ListNode n8 = new ListNode(12, n9);
        ListNode n7 = new ListNode(12, n8);
        ListNode n6 = new ListNode(12, n7);
        ListNode n5 = new ListNode(12, n6);
        ListNode n4 = new ListNode(12, n5);
        ListNode n3 = new ListNode(12, n4);
        ListNode n2 = new ListNode(12, n3);
        ListNode n1 = new ListNode(12, n2);

        n12.next = n8;

        System.out.println(hasCycle(n1));
    }
}
